package bbc;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;

public class test01 {
    public static void main(String[] args) {
        int[] arr = new int[]{4,3,2,1,3,0,5,0,1};
        int totalWaterStorage = findTotalWaterStorage(arr);
        System.out.println(totalWaterStorage
        );

    }


    private static int findTotalWaterStorage(int[] waterArray) {

        int totalWater = 0;

        // 最高点的值
        int maxHeight = waterArray[0];
        // 最高点的位置
        int maxHeightIndex = 0;

        // 找出最高点的位置和值
        for(int i = 1; i<waterArray.length; i++){
            if(maxHeight < waterArray[i]){
                maxHeight = waterArray[i];
                maxHeightIndex = i;
            }
        }

        /**
         * 隐性前提： leftHeight  一定小于或者等于  maxHeight
         * 隐性前提： rightHeight 一定小于或者等于  maxHeight
         */

        // 从左往右扫描
        int res = 10000;
        int leftHeight = waterArray[0];
        for(int i=1; i<maxHeightIndex; i++){
            // 如果当前遍历的位置是低谷
            if(waterArray[i] < leftHeight){
                totalWater += (leftHeight - waterArray[i]);
            }else{
                // 如果不是低谷，则更换左边的较高位置
                res = Math.min(res,totalWater);
                totalWater = 0;
                leftHeight = waterArray[i];
            }
        }

        // 从右往左
        int rightHeight = waterArray[waterArray.length-1];
        for(int i=waterArray.length-2; i>maxHeightIndex; i--){
            // 如果当前遍历的位置是低谷
            if(waterArray[i] < rightHeight){
                totalWater += (rightHeight - waterArray[i]);
            }else{
                res = Math.min(res,totalWater);
                totalWater = 0;
                // 如果不是低谷，则更换左边的较高位置
                rightHeight = waterArray[i];
            }
        }
        return res;
    }

}
